題目

https://leetcode.com/problems/add-two-numbers/

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解答

C#

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode result = new ListNode(0);
        ListNode current = result;

        while (l1 != null || l2 != null || carry > 0)
        {
            if (l1 != null)
            {
                carry = carry + l1.val;
                l1 = l1.next;
            }

            if (l2 != null)
            {
                carry = carry + l2.val;
                l2 = l2.next;
            }
            current.next = new ListNode(carry % 10);
            carry = carry / 10;
            current = current.next;
        }
        return result.next;
    }
}

結果

Runtime: 104 ms, faster than 97.5% of C# online submissions.

Memory Usage: 26.9 MB, less than 9.09% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

沒錯！今天還是趁大家對 LinkedList 還有熱度的時候，我們來挑戰另一個 Medium 的題目！

想惡補或忘記的人請參考 ↓
[Day 14] 演算法刷題 LeetCode 21. Merge Two Sorted Lists (Easy)
[Day 15] 演算法刷題 LeetCode 141. Linked List Cycle (Easy)
[Day 16] 演算法刷題 LeetCode 142. Linked List Cycle II (Medium)

這題只是要將兩個 LinkedList 相加，而且剛好是倒序的排法

就不用考慮位數位移的問題，唯獨需要注意的是相加時有進位的可能

1. 宣告 int carry 來記錄是否有 進位 的數字
2. 宣告 result 起始為 0，等待串接整個 ListNode
3. 宣告 current 起始為 result，用來計算每個位數
4. 透過 while 迴圈計算，並判斷以下條件
   1. l1 不為 null
   2. 或是 l2 不為 null
   3. 或是 carry 還有值需要進位
      若以上條件擇一成立，代表還有數字需要計算
      • 若是 l1 不為 null
        • 把 l1.val 加到 carry
        • l1 指向下一個 node(next)
      • 若是 l2 不為 null
        • 把 l2.val 加到 carry
        • l2 指向下一個 node(next)
      • 將 carry % 10，加到 current.next，因為 carry 若大於10，我們只取個位數
      • carry 則取 十位數 (carry / 10)，待下一輪時計算
      • current 指向下一個 node(next)
5. 迴圈結束，並回傳 result 第2個 node(result.next)，因為我們起頭先接了一個 0 在前面

是不是跟 [Day 14] 演算法刷題 LeetCode 21. Merge Two Sorted Lists (Easy) 的其中一個寫法有異曲同工之妙啊？

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉